02｜双指针 / 滑动窗口（知识笔记）

对应课程：lessons/02-prefix-diff-two-pointers/02-two-pointers-and-sliding-window.md

识别信号

• 序列/字符串
• 想要 $O(n)$，并且窗口扩张/收缩能维持某个约束

成立前提（最关键的一句话）

左指针只增不减。

这背后需要一种“单调性”：

• 右端点右移会让约束更容易被破坏（或更容易满足），
• 从而左端点只需要单调右移就能恢复（或继续满足）约束。

典型能成立的条件：

• 数组非负 → 窗口和随右移不减
• “至多 K 次/至多 K 种” → 扩张更容易违规，收缩会缓解

两种最常用目标

A) 最短满足窗口

• r 右移直到满足
• l 右移尽量缩小（保持仍满足）

B) 最长满足窗口

• r 右移扩张
• 若违规：l 右移直到重新满足

高频题型

• 至多 K 个不同元素
• 至多 K 次修改/翻转
• 子数组满足某个“可维护”的条件（用计数表/窗口和）

常见坑

• 条件不单调：例如含负数时“窗口和 >= X”并不单调
• 计数表更新顺序写错（先移指针还是先改计数）
• 答案更新时机写错（收缩前/后）

自检

• [ ] 我能保证 l 只增不减吗？如果需要回退，模型大概率错
• [ ] 手推一个最小样例看 l,r 的变化

个人坑位

• （例）我经常在 while 收缩里把 cnt 更新漏掉